A multi-level map structure is used in some conventional solid-state drives to look up physical locations of logical block addresses on a nonvolatile media. The map information is regularly checkpointed. The checkpoint of higher-levels of the multi-level map enables fast boot times since only a small amount of metadata (i.e., the higher levels) is read to enable the drive to respond to host accesses of the logical block addresses. However, an ability to read user data becomes vulnerable with respect to any inaccuracy in the map. If the map loses synchronization due to any firmware problems and/or corruption, some amount or even all of the user data can be rendered inaccessible.